# coding=utf-8
__author__ = 'st316'
'''
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
'''


class Solution:
    # @return a boolean
    def isScramble(self, s1, s2):
        # 动态规划解法
        if len(s1) != len(s2):
            return False
        l = len(s1)
        # dp[k][i][j]表示s2从j开始长度为k的子串是否可以由s1从i开始长度为k的子串转换而成
        dp = [[[False] * l for y in xrange(l)] for x in xrange(l + 1)]
        # 初始化长度为1的子串的dp值
        for i in xrange(l):
            for j in xrange(l):
                dp[1][i][j] = True if s1[i] == s2[j] else False
        for k in xrange(2, l + 1):  # 子串的长度
            for i in xrange(l - k + 1):  # s1的起始位置
                for j in xrange(l - k + 1):  # s2的起始位置
                    dp[k][i][j] = False
                    # divlen表示两个子串分割点到子串起始端的距离
                    divlen = 1
                    while divlen < k and not dp[k][i][j]:
                        dp[k][i][j] = (dp[divlen][i][j] and dp[k - divlen][i + divlen][j + divlen]) or (
                            dp[divlen][i][j + k - divlen] and dp[k - divlen][i + divlen][j])
                        divlen += 1
        return dp[l][0][0]


if __name__ == '__main__':
    s = Solution()
    print s.isScramble('pcighfdjnbwfkohtklrecxnooxyipj', 'npodkfchrfpxliocgtnykhxwjbojie')